package Aleehot100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * ClassName: c062
 * Package: Aleehot100
 * Description: 八皇后问题 :
 *
 * @Author BCXJ
 * @Create 2025/8/13 20:40
 * @Version 1.0
 * @Since 1.0
 */
public class c062 {
    public static void main(String[] args) {
        System.out.println(solveNQueens(4));
    }
    static  List<List<String>> res; // 结果
    static char[][] board;
    static boolean[] cols ;           // 列
    static boolean[] diag1 ;  // 主对角线 左上 到 右下
    static boolean[] diag2 ;  // 副对角线 右上 到 左下
    public static List<List<String>> solveNQueens(int n) {
        char[][] board = new char[n][n]; // 看板
        res = new ArrayList<>();
        // 初始化棋盘为 '.'
        for (int i = 0; i < n; i++) {
            Arrays.fill(board[i], '.');
        }

        cols = new boolean[n];           // 列
        diag1 = new boolean[2 * n - 1];  // 主对角线
        diag2 = new boolean[2 * n - 1];  // 副对角线

        // 判断 是否攻击可控制在O(1)
        backtrack(0, n, board);
        return res;
    }

    // 回溯处理方案
    private static void backtrack(int row, int n, char[][] board) {
        if(row == n) {
            res.add(construct(board)); // 结果已成型
        }

        for (int col = 0; col < n; col++) {
            int d1 = row - col  + n - 1; // 确保范围 在 0 ~ 2n - 1
            int d2 = row + col;
            if(cols[col] || diag1[d1] || diag2[d2]) { // 证明 row,col 是不能放皇后的
                continue;
            }
            // 能放皇后
            board[row][col] = 'Q';
            cols[col] = diag1[d1] = diag2[d2] = true;
            backtrack(row + 1, n, board);

            // 恢复
            cols[col] = diag1[d1] = diag2[d2] = false;
            board[row][col] = '.';
        }

    }


    /**
     * 将看板的数据 装成 String 然后封装为 List<String> 集合
     * @param board
     * @return
     */
    private static List<String> construct(char[][] board) {
        List<String> path = new ArrayList<>();
        for (char[] row : board) {
            path.add(new String(row));
        }
        return path;
    }

}
